implement Iterable(Int) for List[Int] {
    public function iterator(): Box[Iterator[Int]] {
        return this;
    }
}

// iterator style one: use lists themselves as iterators
implement Iterator[Int] for List[Int] {
    public function next(): (Box[Iterator[Int]], Option[Int]) {
        printf("%s\n", "list iterator: next");
        match this {
            Cons(h, t) => {
                printf("returning %i\n", h);
                return (*t, Some(h));
            }
            Empty => {
                printf("empty\n");
                return (this, None);
            }
            default => {
                printf("wtf\n");
                return (this, None);
            }
        }
    }
}

// iterator style two: use a struct to store iterator state
struct ListIterator {
    var listPtr: Ptr[List[Int]];
}

implement Iterable(Int) for ListIterator {
    public function iterator(): Box[Iterator[Int]] {
        return this;
    }
}

implement Iterator[Int] for ListIterator {
    public function next(): (Box[Iterator[Int]], Option[Int]) {
        printf("%s\n", "struct iterator: next");
        match *(this.listPtr) {
            Cons(h, t) => {
                printf("returning %i\n", h);
                this.listPtr = t;
                return (this, Some(h));
            }
            Empty => {
                printf("empty\n");
                return (this, None);
            }
            default => {
                printf("wtf\n");
                return (this, None);
            }
        }
    }
}

function main() {
    var list: List[Int] = Cons(1, &Cons(2, &Cons(3, &Empty)));
    var iterable: Box[Iterable] = list;
    var iterator: Box[Iterator[Int]] = iterable.iterator();

    printf("list iterator manual iteration\n");
    printf("length = %zu\n", list.getLength());
    // manual iteration
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();

    // refresh the iterator
    printf("list iterator for loop iteration\n");
    iterator = iterable.iterator();

    printf("length = %zu\n", list.getLength());

    for current in list {
        printf("for loop over collection: %i\n", current);
    }
    printf("done\n");

    for current in iterator {
        printf("for loop over iterator: %i\n", current);
    }
    printf("done\n");

    var iteratorStruct: ListIterator = struct ListIterator {
        listPtr: list
    };
    iterator = iteratorStruct;

    printf("struct iterator for loop iteration\n");
    printf("length = %zu\n", list.getLength());
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();
    (iterator, _) = iterator.next();

    iteratorStruct.listPtr = list;
    iterator = iteratorStruct;

    printf("struct iterator manual iteration\n");
    printf("length = %zu\n", list.getLength());

    for x in iteratorStruct {
        if x == 1 {
            continue;
        }
        printf("for loop over iterable: %i\n", x);
    }
    printf("done\n");
}
